import java.util.ArrayList;
import java.util.List;

public class Solution84 {
    public int largestRectangleArea(int[] heights) {
        List<Integer> low = new ArrayList<>();
        int[] dp = new int[heights.length];
        dp[0] = heights[0];
        for (int i = 1; i < heights.length; i++) {
            if (heights[i] > heights[i - 1]) {
                low.add(i - 1);
                dp[i] = heights[i];
            } else {
                int j = low.size() - 1;
                for (; j >= 0; j--) {
                    int left = low.get(j);
                    if (heights[left] < heights[i]) {
                        dp[i] = heights[i] * (i - left);
                        break;
                    }
                }
                if (j < 0) {
                    dp[i] = heights[i] * (i + 1);
                }
            }

        }
        low.clear();
        for (int i = heights.length - 2; i >= 0; i--) {
            if (heights[i] > heights[i + 1]) {
                low.add(i + 1);
            } else {
                int j = low.size() - 1;
                for (; j >= 0; j--) {
                    int right = low.get(j);
                    if (heights[right] < heights[i]) {
                        dp[i] += heights[i] * (right - i - 1);
                        break;
                    }
                }
                if (j < 0) {
                    dp[i] += heights[i] * (heights.length - i - 1);
                }
            }
        }
        int res = dp[0];
        for (int i : dp) {
            if (i > res) {
                res = i;
            }
        }
        return res;
    }
}
